COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input basic
C00004 00003	\ctrline{\bf Common Lisp Development}
C00008 00004	\vskip .25truein
C00014 00005	\vskip .25truein
C00019 00006	\vskip .25truein
C00023 00007	\vskip .25truein
C00025 00008	\ctrline{\bf Attachment}
C00032 ENDMK
C⊗;
\input basic
\jpar 1000
\varunit 1truein
\parskip .15in plus 5pt \baselineskip 15pt \lineskip 1pt
\def\rm{\:a} \def\sl{\:n} \def\bf{\:q} \def\it{\:?}
\font m=cmsc10 		%  Small caps
\def\sc{\:m}		%  Small Caps  (10pt)
\output{\baselineskip 18pt\page}

\ctrline{\bf Common Lisp Development}
\vskip 1truein
\ctrline{\bf Proposal to}
\ctrline{\bf The Defense Advanced Research Projects Agency}
\vskip 3truein
\ctrline{\bf Principal Investigator}
\vskip 1truein
\ctrline{\bf John McCarthy}
\ctrline{\bf Professor of Computer Science}
\ctrline{\bf Stanford University}
\vfill\eject
\output{\baselineskip 18pt\page\ctrline{\curfont a\count0}\advcount0}
\ctrline{\bf Common Lisp Development}
\vskip .5truein
\ctrline{by}
\vskip .5truein
\ctrline{John McCarthy}
\ctrline{Professor of Computer Science}
\ctrline{Stanford University, Stanford, CA 94305}
\vskip .5truein
\ctrline{Proposed research:}
\ctrline{Advanced Research Projects Agency}
\ctrline{June 1, 1983---December 31, 1985}
\vskip 1truein

Common Lisp is the combined effort of eight different Lisp implementation
groups aimed at producing a common dialect of Lisp while allowing each
group to exploit its own hardware.  These groups are: Spice Lisp at CMU,
DEC Common Lisp on Vax at CMU, DEC Common Lisp on DEC-20 at Rutgers, S-1
Lisp at LLNL, Symbolics Common Lisp, LMI Common Lisp, Portable Standard
Lisp at Utah, and Vax NIL.  Common Lisp is a set of documents, a language
design, and a common body of code.

The main goal of Common Lisp is to unify the experiences of the
Lisp implementations that are descended, either historically or
philosophically, from MacLisp. MacLisp is a dialect of Lisp that
emphasizes ease of system-building and efficient execution of numeric
code.  

Other goals of Common Lisp are to provide a workbench programming
language for artificial intelligence, symbolic algebra, robotics,
and education for the next decade. With such a commonly available
and commonly used Lisp it would be possible for researchers to
exchange programs with a minimum of effort, even though the host
computers could be very different. Such a Lisp would be powerful enough
to write a sophisticated operating system sufficient to support its
own use and would, thereby, prove to be a useful systems research tool
as well as a tool for creating Lisp machine environments.

With a powerful Lisp widely available, research centers might not have
to consider the language features of the Lisp(s) available on various
computers as part of the decision regarding what hardware to purchase.
In this way a more intelligent and effective choice could be made.

Common Lisp should support an easily-understood, portable programming style.
By making a large number of packages written in Lisp available it is hoped 
that not only would the amount of work needed to get a system running be
low, but the overall programming style and methodology would be improved
through exposure to the code written by expert programmers.

\vskip .25truein
\ctrline{\bf History}

After the usefulness of the PDP-10 as a Lisp engine declined because its
address space was limited to 18 bits, several implementation groups
started to implement Lisps for computers with larger address spaces, and
these implementors tried to improve and extend MacLisp, both to take
advantage of lessons learned from MacLisp and the various languages built
on top of it (Scheme, for example) and to also exploit the architectures
the implementors were using.

It soon became clear to several of the implementors (Richard Gabriel of
Stanford and Lawrence Livermore National Laboratory, Guy L. Steele Jr. of
Carnegie-Mellon University, Jon L. White then of the Massachusetts
Institute of Technology, and Scott Fahlman of Carnegie-Mellon University)
that the situation of four different Lisps---Vax NIL, SPICE Lisp, Lisp
Machine Lisp, and Franz Lisp---all descended from MacLisp, all used by
ARPA-sponsored institutions, and each different from the others in subtle,
yet important, ways, was intolerable to the research community. Several
key meetings among the implementors resulted in an initial commitment to
unify the approaches in the form of a large, common subset, which was to
be called `Common Lisp.' Of the four major Lisp implementations, only
Franz Lisp did not appear interested in joining the Common Lisp group, and
for financial rather than philosophical reasons.

Since this informal group got together, the language, Common Lisp,
has been largely designed and a manual written that describes the
language at user-level.  The original informal group has expanded into a
larger, formal committee which is collaborating on the language design and
documentation in a loose fashion. This group, called the `Common Lisp
Group', maintains a mailing list and an archive of working messages at
SAIL (Stanford Artificial Intelligence Laboratory).
Many decisions have been made about the political organization of Common
Lisp and about what the manual does and does not require of an
implementation.

To be most useful, Common Lisp must support a large body of packages and
routines, so that a tradition of code, so to speak, is maintained. For
example, pattern matchers, object-oriented programming packages, and
indexing routines should be available so that projects requiring these
tools can use existing, well-tested code. In addition, these packages
ought to be of certified quality of functionality and documentation.

If Common Lisp is to be widely used it must be available on hardware not
currently supporting Common Lisp dialects. Since Common Lisp is a large
language, producing a working Common Lisp simply from the manual would
require several man-years of effort. One of the next tasks to be
undertaken is to define Common Lisp in terms of a {\sl virtual machine}
description.

Such a description is a formal definition of a number of primitives that
must be defined on the hardware in question. Then the remainder of Common
Lisp is defined as a body of Common Lisp code written with the assumption
that these primitives exist. Once these primitives are defined on a piece
of hardware, a Common Lisp interpreter is gained by `loading' the body of
Common Lisp code.

\vfill\eject
\vskip .25truein
\ctrline{\bf Documentation for Common Lisp}

Currently Common Lisp is nothing more than an organization for
documentation along with some of that documentation. To be complete
as envisioned by the Common Lisp Group, the rest of the documentation
must be brought into existence.

The Common Lisp documentation is divided into four parts, known as the
{\sl white pages}, the {\sl yellow pages}, the {\sl red pages}, 
and the {\sl blue pages}.

The {\sl white pages} is a language specification rather than an implementation
specification.  It defines a set of standard language concepts and
constructs that may be used for communication of data structures and
algorithms in the Common Lisp dialect.  This is sometimes referred to as
the ``core Common Lisp language,'' because it contains conceptually
necessary or important features.  It is not necessarily implementationally
minimal.  While some features could be defined in terms of others by
writing Lisp code (and indeed may be implemented that way), it was felt
that these features should be conceptually primitive so that there might
be agreement among all users as to their usage.  (For example, bignums and
rational numbers could be implemented as Lisp code given operations on
fixnums.  However, it is important to the conceptual integrity of the
language that they be regarded by the user as primitive, and they are
useful enough to warrant a standard definition.)

The {\sl yellow pages} is a program library document, containing documentation
for assorted and relatively independent packages of code.  While the white
pages are to be relatively stable, the yellow pages are extensible; new
programs of sufficient usefulness and quality will routinely be added from
time to time.  The primary advantage of the division into white and yellow
pages is this relative stability; a package written solely in the
white-pages language should not break if changes are made to the
yellow-pages library.

The {\sl red pages} is implementation-dependent documentation; there will
be one set for each implementation.  Here are specified such
implementation-dependent parameters as word size, maximum array size,
sizes of floating-point exponents and fractions, and so on, as well as
implementation-dependent functions such as input/output primitives.

The {\sl blue pages} constitutes an implementation guide in the spirit of the
Interlisp virtual machine specification.  It specifies a subset of the
white pages that an implementor must construct, and indicates a quantity
of Lisp code written in that subset that implements the remainder of the
white pages.  In principle there could be more than one set of blue pages,
each with a companion file of Lisp code.  (For example, one might assume
{\sc IF} to be primitive and define {\sc COND} as a macro in terms of IF, while
another might do it the other way around.)

\vfill\eject
\vskip .25truein
\ctrline{\bf The Proposal}

At present the white pages portion of Common Lisp is nearly complete, that
document being edited by Guy Steele Jr. at CMU. Since Guy Steele is
taking a leave-of-absence from CMU to work at Tartan Labs, and since Scott
Fahlman, the head of the Spice Lisp project and a major contributor to
Common Lisp, wants to return to his AI research, the administrative
control of the Common Lisp effort is in question with several important
parts left undone. Stanford University proposes to complete those parts.

In particular we propose to do three things.  We will complete the white
pages: though Guy Steele will be able to work several hours a week on that
task while at Tartan Labs, it may prove impractical for him to spend all
the time needed for the job. We will help him finish the writing and
editing, arrange and direct the Common Lisp Group meetings, and perform
the administrative work necessary to complete the language specification
and documentation.

We will produce the first version of the yellow pages. This task consists
of gathering proposed packages, validating the documentation, insuring the
portability, and doing some testing of the code before it is included in
the yellow pages. All code will be uniformly housed at Stanford with
access to all ARPA contractors.  This document and library is to be
completed by the end of December 1984.

Finally, and most importantly, we will produce the first version of the
blue pages. This requires producing a detailed specification of the subset
of the white pages that must be implemented by an implementation group to
support Common Lisp, expanding on the white pages description where
necessary. We will also write, test, and document an implementation of
Common Lisp in that subset and make that code available to anyone wanting
to implement a Common Lisp. Thus, for any group to implement a Common
Lisp, all that will need to be done is to write the specified language
subset in whatever other language their hardware supports and to then take
a copy of the Lisp code we will have produced which will complete the
implementation of the white pages language.  This document and code is to
be completed by the end of December 1985.

\vskip .25truein
\ctrline{\bf Compiler}

Of course, the blue pages is not complete without a portable compiler.
Such a compiler could be of the form of a machine-independent portion and
a machine-dependent portion. The machine-independent portion can perform
source-to-source transformations, flow analysis, data-structure analysis,
tail-recursion analysis, and environment analysis. The machine-dependent
portion can perform target annotation, register allocation, and code
generation. The S-1 compiler for Common Lisp is largely structured this
way. Many of the machine-dependent parts are table-driven. This compiler
could be adapted for use as a portable Common Lisp compiler.

The generation of a complete Common Lisp can be made relatively simple using
a compiler which compiles {\sl sub-primitives} such as those necessary for
doing storage allocation and performing garbage collection. The S-1 Common Lisp
system is built this way, and only about 400 lines of assembly language code
is required to build the Lisp system.

We propose to investigate the feasibility of a portable compiler by doing a
preliminary restructuring of the S-1 Lisp compiler and by examining the
structure of the Utah Portable Standard Lisp compiler. 

\vfill\eject
\ctrline{\bf Attachment}

Attached to this report is a budget projection.

\vskip 2truein
\ctrline{Salaries}

$$\vcenter{\halign to size{#\hfill\tabskip 0pt plus 100pt
⊗\hfill #⊗\hfill #⊗\hfill #\tabskip 0pt\cr
Item⊗1983⊗1984⊗1985\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Research Associate⊗30,000⊗33,000⊗36,300\cr
Support⊗1,000⊗1,100⊗1,250\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Salaries⊗31,000⊗34,100⊗37,510\cr
Benefits⊗6,510⊗7,161⊗7,877\cr}}$$

\ctrline{Direct Costs}

$$\vcenter{\halign to size{#\hfill\tabskip 0pt plus 100pt
⊗\hfill #⊗\hfill #⊗\hfill #\tabskip 0pt\cr
Item⊗1983⊗1984⊗1985\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Four Trips per Year⊗2,000⊗2,300⊗2,645\cr
Expendables⊗750⊗865⊗1000\cr
Publications⊗1,000⊗1,100⊗1,250\cr
Computer Use⊗12,000⊗14,400⊗17,280\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Direct Costs⊗53,260⊗59,926⊗67,562\cr
Total Indirect Costs⊗36,750⊗41,349⊗46,618\cr\noalign{\vskip 2pt\hrule\vskip 2pt}
Total Costs⊗$\$$90,009⊗$\$$101,275⊗$\$$114,180\cr}}$$

\vfill\end